/*
Largest Number Total Accepted: 22784 Total Submissions: 144494 My Submissions Question Solution
Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.
*/

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include <unordered_map>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}


/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
	static bool cmp(const string &str1, const string &str2)
	{
		return (str1 + str2) > (str2 + str1);
	
	}

	string largestNumber(vector<int>& nums) {
		vector<string> strNum(nums.size());

		for (int i = 0; i < nums.size(); i++)
		{
			strNum[i] = to_string(nums[i]);

		}

		sort(strNum.begin(),strNum.end(),cmp);

		string res;
		bool flag = false;

		for (int i = 0; i < strNum.size(); i++)
		{
			if (strNum[i] != "0")
			{
				res += strNum[i];
				flag = true;
			}
			else if (flag)
			{
				res += strNum[i];
			}

		}

		if (!flag)res.push_back('0');
		return res;

	}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

int main(int argc, char* argv[])
{

	int a[] = { 3, 30, 34, 5, 9 };
	vector<int> nums(a,a+sizeof(a)/sizeof(int));
	
	string strRes;


	
	Solution s;
	strRes = s.largestNumber(nums);
	//cout << "The result is : " << result << endl;
	//result = s.partition(str);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s.isPalindrome(str1))
	//	cout << " True" << endl;
	//else
	//	cout << "false" << endl;
	system("pause");
	return 0;
}
//std::unordered_set<std::string> myset =
//{ "hot", "dot", "dog", "lot", "log" };

//std::cout << "myset contains:";
// for (auto it = myset.begin(); it != myset.end(); ++it)
//std::cout << " " << *it;
//;; std::cout << std::endl;

//TreeNode *root = new TreeNode(1);
//TreeNode *left = new TreeNode(2);
//TreeNode *right = new TreeNode(3);

//root->left = left;
//root->right = right;s